講義概要/Class Outline

アルゴリズム論Iに引き続き、アルゴリズムの実行時間を解析する手法について学ぶ。本講義では、繰返しなどの複雑な構造を持つアルゴリズムを対象とする。  

講義計画 /Class Structure

回	内容
1	講義概要 講義概要と計画について説明する。
2	アルゴリズムの正当性と数学的証明 アルゴリズムの正当性を示すために、数学的証明を与えることの重要性について解説する。
3	数列 繰返し構造を持つアルゴリズムの理解と解析には、数列の考え方が有用であるので、数列に関する学習を行う。
4	数学的帰納法 繰返し構造を持つアルゴリズムの正当性を示す手法の基礎として、数学的帰納法を学ぶ。
5	繰返しのあるアルゴリズム 自然数の和問題を取り上げ、繰返しのあるアルゴリズムに対して実行時間の解析と正当性の証明を行う。
6	Θ記法とＯ記法 Θ記法とＯ記法を用いた実行時間の解析について解説する。
7	小テスト１ 第６回までの内容についてテストを行う。
8	補足と復習 テストの解説ならびに補足と復習を行う。
9	探索問題（１） 探索問題に対するアルゴリズムとその正当性について解説する。
10	探索問題（２） 探索問題に対するアルゴリズムの平均実行時間と最悪実行時間について解析する。
11	再帰アルゴリズム 再帰構造をもつアルゴリズムに対して、最悪実行時間を解析する。
12	整列問題 データを整列する問題に対するアルゴリズムを紹介する。
13	小テスト２ 第８回から第１２回の内容についてテストを行う。
14	補足と復習 テストの解説ならびに補足と復習を行う。